package checker.algorithms.sort.primarySort;

import checker.algorithms.sort.SortBase;

public class Shell extends SortBase {
    /**
     * 每次都从i到length，序列从后往前，保证序列不会被后面的排序打乱
     * @param a
     */
    @Override
    public void sort(Comparable[] a) {
        int length = a.length;

        int h = 1;

        while ((h * 3 + 1) < length) {
            h = h * 3 + 1;
        }

        while (h > 0) {
            // 排序为h有序，i=h开始
            for (int i = h; i < length; i++) {
                // 排序为0-i的h有序序列, j >= 0, 但防止j-h 溢出
                for (int j = i; j >= h; j = j - h) {
                    if (less(a[j], a[j - h])) {
                        exch(a, j, j - h);
                    }

                }

            }
            // (h*3+1)/3 = h + 1/3（int会丢弃小数部分） = h
            h = h / 3;
        }

        System.out.println(isSorted(a));
    }

    public static void main(String[] args) {
        new Shell().run();
    }
}
